package leetcode.code;

import java.util.PriorityQueue;

/**
 * 给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。
 *
 *  
 *
 * 示例：
 *
 * 给出如下 3x6 的高度图:
 * [
 *   [1,4,3,1,3,2],
 *   [3,2,1,3,2,4],
 *   [2,3,3,2,3,1]
 * ]
 *
 * 返回 4 。
 *
 *
 * 如上图所示，这是下雨前的高度图[[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] 的状态。
 *
 *  
 *
 *
 *
 * 下雨后，雨水将会被存储在这些方块中。总的接雨水量是4。
 *
 *  
 *
 * 提示：
 *
 * 1 <= m, n <= 110
 * 0 <= heightMap[i][j] <= 20000
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/trapping-rain-water-ii
 *
 */

public class 接雨水II {
    /*
     * 暴力
     * 通过遍历边界 然后通过最小堆 寻找最低点
     */
    public static int trapRainWater(int[][] heightMap) {
        int width = heightMap[0].length;
        int height = heightMap.length;
        if (width<3 || height<3){return 0;}
        // 标记
        boolean[][] flags = new boolean[width][height];
        // 最小堆
        PriorityQueue<int[]> queue = new PriorityQueue<>( (o1,o2) -> o1[2]-o2[2] );
        // 存放的三元组 (x,y,height) 注意 x指横坐标 y指纵坐标
        // 初始化边界
        for (int i = 0; i < width; i++){
            queue.offer(new int[]{i, 0, heightMap[0][i]});
            queue.offer(new int[]{i, height-1, heightMap[height-1][i]});
        }
        for (int i = 1; i < height-1; i++){
            queue.offer(new int[]{0, i, heightMap[i][0]});
            queue.offer(new int[]{width-1, i, heightMap[i][width-1]});
        }
        int sum = 0;
        // 方向数组
        int[] dirs = new int[]{-1, 0, 1, 0, -1};
        while (!queue.isEmpty()){
            int[] poll = queue.poll();
            // 查找四个方向
            for (int k = 0; k < 4; k++){
                // 目标点坐标
                int x = poll[0] + dirs[k];
                int y = poll[1] + dirs[k+1];
                // 判断合法性且应未被标记过 且不应是最外围节点
                if (x>0 && x<width-1 && y>0 && y<height-1 && !flags[x][y]){
                    // 如果目标点低于外边界中的最低点则说明可以蓄水
                    if (poll[2] > heightMap[y][x]){
                        sum += poll[2] - heightMap[y][x];
                        // 注满水以后添加进去
                        queue.offer(new int[]{x, y, poll[2]});
                    }else {
                        queue.offer(new int[]{x, y, heightMap[y][x]});
                    }
                    flags[x][y] = true;
                }
            }
        }
        return sum;
    }

    public static void main(String[] args){
        int[][] a = new int[][]{{9,9,9,9,9,9,8,9,9,9,9},{9,0,0,0,0,0,1,0,0,0,9},{9,0,0,0,0,0,0,0,0,0,9},{9,0,0,0,0,0,0,0,0,0,9},{9,9,9,9,9,9,9,9,9,9,9}};
        System.out.println(trapRainWater(a));
    }
}
